﻿
// 第 k 个数：
//给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
//
//输入格式
//第一行包含两个整数 n 和 k。
//
//第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
//
//输出格式
//输出一个整数，表示数列的第 k 小数。
//
//数据范围
//1≤n≤100000,
//1≤k≤n
//输入样例：
//5 3
//2 4 1 5 3
//输出样例：
//3


//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//int arr[N];
//
//void my_qsort(int left, int right) {
//	if (left >= right) return;
//
//	int target = arr[left + right >> 1], pre = left - 1, cur = right + 1;
//	while (pre < cur) {
//		do {
//			pre++;
//		} while (arr[pre] < target);
//		do {
//			cur--;
//		} while (arr[cur] > target);
//
//		if (pre < cur)
//			swap(arr[pre], arr[cur]);
//	}
//
//	my_qsort(left, cur);
//	my_qsort(cur + 1, right);
//}
//
//int main(void) {
//	int n, k;
//	cin >> n >> k;
//	for (int i = 0; i < n; i++) cin >> arr[i];
//
//	my_qsort(0, n - 1);
//
//	cout << arr[k - 1] << endl;   // 第 k 个元素的下标是 k - 1 的哦
//
//	return 0;
//}